FIG. 1 depicts a functional block diagram of a portion of an operating system 100 including a memory manager 102 responsible for allocating and de-allocating pieces of memory from a memory pool 104 to requesting processes, e.g., internal memory requester 106 and external memory requester 108, and de-allocating memory space freed from a requesting process to the memory pool. Internal memory requester 106 includes processes, e.g., sets of executable instructions, providing functionality such as one or more of user interface, job management, task management, data management, device management, security and other functionality, within operating system 100 which request memory pieces from memory manager 102. External memory requester 108 includes processes providing functionality such as word processors, web browsers, spreadsheets, photo manipulation software, and other software not a part of the operating system, external to the operating system which request memory pieces from memory manager 102. Memory pool 104 may be a hardware component, a software component, or combined component thereof providing a storage capability.
In response to a request for a piece of memory from one of memory requesters 106, 108, memory manager 102 allocates a piece of memory from memory pool 104. In other instances, memory manager 102 allocates more than one piece of memory at a time.
Memory requesters 106, 108 return allocated memory to memory manager 102 which, in turn, either returns the de-allocated memory to memory pool 104 or re-allocates the memory to one of memory requesters 106, 108 in response to a new request. In returning memory to memory pool 104, memory manager 102 waits until receiving an entire page of memory de-allocated from one or more memory requesters 106, 108 before returning the memory to memory pool 104. That is, memory manager 102 only returns complete pages of memory to memory pool 104.
Due to the unpredictable nature of memory de-allocation by memory requesters 106, 108, it is possible that a memory requester 106, 108 may retain portions of memory indefinitely and thereby prevent the return of a page of memory to memory pool 104. In a period of high memory usage by memory requesters 106, 108, memory manager 102 may acquire and allocate multiple pages of memory from memory pool 104 to the memory requesters. After the high memory usage period passes, memory manager 102 attempts to gather the allocated pages of memory for return to memory pool 104. If a portion of each previously allocated page of memory remains in use by one of the memory requesters 106, 108, memory manager 102 is unable to recover an entire page of memory for return to memory pool 104.
During the period that memory manager 102 attempts to recover entire pages of memory for return to memory pool 104, the memory manager receives additional memory requests from memory requesters 106, 108. Frequently, memory manager 102 fulfills the received memory request by using pieces of pages of memory that have been returned by a previous memory requestor. Thus, reallocation of memory by memory manager 102 in response to memory requests increases the difficulty of gathering all the pieces of any particular page in order to return the page to memory pool 104.
Memory managers, such as memory manager 102, generally operate in one of two ways storing returned memory from memory requesters 106, 108: a first-in, first-out (FIFO) queue and a last-in, first-out (LIFO) queue. A FIFO queue results in the least recently returned memory portion being soonest allocated. A LIFO queue results in recently returned pieces of memory being soonest allocated.